package fina.mirror;

import thired.class18_Mirrors.Class01_MirrisTraversal;

public class Mirrors {
    //如果无左树 cur右移
    //有左树 左树最右指针 mostRight
    //mostRight 指向null  指向 cur 左移
    //mostRight 指向cur 指向null cur右移
    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    public static void mirror(Node root){
        if(root == null){
            return;
        }
        Node cur = root;
        Node mostRightNode = null;
        while(cur != null){
            mostRightNode = cur.left;
            if(mostRightNode != null){
                while (mostRightNode.right != null && mostRightNode.right != cur ){
                    mostRightNode = mostRightNode.right;
                }
                if(mostRightNode.right == null){
                    mostRightNode.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRightNode.right =  null;
                }
            }
            cur = cur.right;
        }
    }
    public static void mirrorPre(Node root){
        if(root == null){
            return;
        }
        Node cur = root;
        Node mostRightNode = null;
        while(cur != null){
            mostRightNode = cur.left;
            if(mostRightNode != null){
                while (mostRightNode.right != null && mostRightNode.right != cur ){
                    mostRightNode = mostRightNode.right;
                }
                if(mostRightNode.right == null){
                    System.out.print(cur.value);
                    mostRightNode.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRightNode.right =  null;
                }
            }else{
                System.out.print(cur.value);
            }
            cur = cur.right;
        }
    }
    public static void mirrorIn(Node root){
        if(root == null){
            return;
        }
        Node cur = root;
        Node mostRightNode = null;
        while(cur != null){
            mostRightNode = cur.left;
            if(mostRightNode != null){
                while (mostRightNode.right != null && mostRightNode.right != cur ){
                    mostRightNode = mostRightNode.right;
                }
                if(mostRightNode.right == null){
                    mostRightNode.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    System.out.print(cur.value);
                    mostRightNode.right =  null;
                }
            }else{
                System.out.print(cur.value);
            }
            cur = cur.right;
        }
    }
    //第二次时逆序打印左树右边界，最后逆序打印整棵树右边界
    //最后那步链表反转
    public static void mirrorPos(Node root){
        if(root == null){
            return;
        }
        Node cur = root;
        Node mostRightNode = null;
        while(cur != null){
            mostRightNode = cur.left;
            if(mostRightNode != null){
                while (mostRightNode.right != null && mostRightNode.right != cur ){
                    mostRightNode = mostRightNode.right;
                }
                if(mostRightNode.right == null){
                    mostRightNode.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRightNode.right =  null;
                    //逆序打印cur 左树右边界
                    printReverse(cur.left);
                }
            }
            cur = cur.right;
        }
        //逆序打印整棵树右边界
        printReverse(root);
    }

    public static void printReverse(Node head){
        if(head == null) return;
        Node tail = reverse(head);
        //todo print
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverse(tail);
    }
    public static Node reverse(Node head){
        Node pre = null;
        Node cur = head;
        Node next = null;
        while (cur != null){
            next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
//        printTree(head);
        mirrorIn(head);
        System.out.println();
        mirrorPre(head);
        //morrisPos(head);
//        printTree(head);
        System.out.println();
        System.out.println("===================");

    }
}